#include "stack_queue.h"
#include <iostream>
#include <string>
using namespace std;

void MyStack::printStack()
{
    listNode *p = topNode;

    while (p != NULL)
    {
        if (p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
    }
}

void MyQueue::printQueue()
{
    int cursor = front;

    while (cursor != rear)
    {
        if ((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

listNode::listNode()
{
    next = NULL;
    data = 0;
}

listNode::listNode(int nodeData, listNode *succ)
{
    data = nodeData;
    next = succ;
}

MyStack::MyStack()
{
    topNode = NULL;
    stackSize = 0;
}

MyStack::~MyStack()
{
    while (topNode != NULL)
    {
        listNode *cur = topNode;
        topNode = topNode->next;
        delete cur;
    }
}

bool MyStack::push(const int &value)
{
    listNode *newNode = new listNode(value, topNode);
    topNode = newNode;
    stackSize++;
    return true;
}

bool MyStack::pop(int &item)
{
    if (topNode == NULL)
    {
        return false;
    }
    item = topNode->data;
    listNode *temp = topNode;
    topNode = topNode->next;
    delete temp;
    stackSize--;
    return true;
}

bool MyStack::getTop(int &item)
{
    if (topNode == NULL)
    {
        return false;
    }
    item = topNode->data;
    return true;
}

MyQueue::MyQueue(const int &size)
{
    capacity = size;
    queue = new int[capacity];
    front = 0;
    rear = 0;
}

MyQueue::~MyQueue()
{
    delete[] queue;
}

bool MyQueue::enQueue(const int &value)
{
    if (isFull())
    {
        return false;
    }
    queue[rear] = value;
    rear = (rear + 1) % capacity;
    return true;
}

bool MyQueue::deQueue(int &item)
{
    if (isEmpty())
    {
        return false;
    }
    item = queue[front];
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int &item)
{
    if (isEmpty())
    {
        return false;
    }
    item = queue[front];
    return true;
}

bool MyQueue::isEmpty()
{
    if (front == rear)
    {
        return true;
    }
    return false;
}

bool MyQueue::isFull()
{
    if ((rear + 1) % capacity == front)
    {
        return true;
    }
    return false;
}

char Precede(char c1, char c2)
{
    int c_temp1 = 0, c_temp2 = 0;
    switch (c1)
    {
    case '*':
    case '/':
        c_temp1 = 5;
        break;
    case '+':
    case '-':
        c_temp1 = 3;
        break;
    case '(':
        c_temp1 = 1;
        break;
    case ')':
        c_temp1 = 8;
        break;
    case '#':
        c_temp1 = 0;
        break;
    default:
        break;
    }
    switch (c2)
    {
    case '*':
    case '/':
        c_temp2 = 4;
        break;
    case '+':
    case '-':
        c_temp2 = 2;
        break;
    case '(':
        c_temp2 = 8;
        break;
    case ')':
        c_temp2 = 1;
        break;
    case '#':
        c_temp2 = 0;
        break;
    default:
        break;
    }
    if (c_temp1 < c_temp2)
    {
        return '<';
    }
    if (c_temp1 == c_temp2)
    {
        return '=';
    }
    if (c_temp1 > c_temp2)
    {
        return '>';
    }
    return 0;
}

bool postfixExpression(const string &expression, string &result)
{
    MyStack OPTR;
    OPTR.push('#');
    long long unsigned int i = 0;
    int a = 0, b = 0;
    while (i < expression.length())
    {
        if (int(expression[i]) >= 48 && int(expression[i]) <= 57)
        {
            result += expression[i];
            i++;
        }
        else
        {
            OPTR.getTop(a);
            switch (Precede(char(a), expression[i]))
            {
            case '<': // 栈顶元素优先权低，符号入栈
                OPTR.push(expression[i]);
                i++;
                break;
            case '=': // 脱括号
                OPTR.pop(b);
                i++;
                break;
            case '>': // 栈顶元素优先权高，符号出栈并写入result
                OPTR.pop(b);
                result += b;
                break;
            default:
                break;
            }
        }
    }
    OPTR.getTop(a);
    while (a != '#')
    {
        OPTR.pop(b);
        result += char(b);
        OPTR.getTop(a);
    }
    for (char c : result)
    {
        if (c == '(' || c == ')')
        {
            result = "Expression is wrong!";
            return false;
        }
    }
    return true;
}

bool expressionVal(const string &expression, int &val)
{
    MyStack OPTR, OPND;
    OPTR.push('#');
    long long unsigned int i = 0;
    int a = 0, b = 0, c = 0;
    while (i < expression.length())
    {
        if (int(expression[i]) >= 48 && int(expression[i]) <= 57)
        {
            OPND.push(int(expression[i]) - 48);
            i++;
        }
        else
        {
            OPTR.getTop(a);
            switch (Precede(char(a), expression[i]))
            {
            case '<': // 栈顶元素优先权低，符号入栈
                OPTR.push(expression[i]);
                i++;
                break;
            case '=': // 脱括号
                OPTR.pop(b);
                i++;
                break;
            case '>': // 栈顶元素优先权高，符号出栈并写入result
                OPTR.pop(a);
                OPND.pop(b);
                OPND.pop(c);
                if (a == '+')
                {
                    val = c + b;
                    OPND.push(val);
                }
                else if (a == '-')
                {
                    val = c - b;
                    OPND.push(val);
                }
                else if (a == '*')
                {
                    val = c * b;
                    OPND.push(val);
                }
                else if (a == '/')
                {
                    val = c / b;
                    OPND.push(val);
                }
                break;
            default:
                break;
            }
        }
    }
    OPTR.getTop(a);
    while (a != '#')
    {
        OPTR.pop(a);
        OPND.pop(b);
        OPND.pop(c);
        if (a == '+')
        {
            val = c + b;
            OPND.push(val);
        }
        else if (a == '-')
        {
            val = c - b;
            OPND.push(val);
        }
        else if (a == '*')
        {
            val = c * b;
            OPND.push(val);
        }
        else if (a == '/')
        {
            val = c / b;
            OPND.push(val);
        }
        OPTR.getTop(a);
    }
    return true;
}

LinkQueue::LinkQueue()
{
    first = new listNode;
    rear = first;
    queueSize = 0;
}

bool LinkQueue::enQueue(const int &val)
{
    listNode *newNode = new listNode;
    rear->next = newNode;
    newNode->data = val;
    rear = newNode;
    queueSize++;
    return true;
}

int LinkQueue::deQueue()
{
    int val;
    listNode *temp;
    temp = first->next;
    val = temp->data;
    first->next = temp->next;
    delete temp;
    return val;
}

void yanghui(const int &n)
{
    LinkQueue q;
    q.enQueue(1);
    q.enQueue(1); // 预放入第一行的两个系数
    int s = 0;
    for (int i = 1; i <= n; i++)
    {
        q.enQueue(0);
        for (int j = 1; j <= i + 2; j++)
        {
            int t = q.deQueue();
            q.enQueue(s + t);
            s = t;
            if (j == i + 1)
            {
                cout << s;
            }
            else if (j != i + 2)
            {
                cout << s << ",";
            }
        }
        cout << endl;
    }
}